home *** CD-ROM | disk | FTP | other *** search
/ Space & Astronomy / Space and Astronomy (October 1993).iso / mac / VIEWERS / MSDOS / GIFLIB12.ZIP / LIB / GIF_HASH.C < prev    next >
C/C++ Source or Header  |  1990-09-06  |  6KB  |  156 lines
  1. /*****************************************************************************
  2. *   "Gif-Lib" - Yet another gif library.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber            IBM PC Ver 0.1,    Jun. 1989    *
  5. ******************************************************************************
  6. * Module to support the following operations:                     *
  7. *                                         *
  8. * 1. InitHashTable - initialize hash table.                     *
  9. * 2. ClearHashTable - clear the hash table to an empty state.             *
  10. * 2. InsertHashTable - insert one item into data structure.             *
  11. * 3. ExistsHashTable - test if item exists in data structure.             *
  12. *                                         *
  13. * This module is used to hash the GIF codes during encoding.             *
  14. ******************************************************************************
  15. * History:                                     *
  16. * 14 Jun 89 - Version 1.0 by Gershon Elber.                     *
  17. *****************************************************************************/
  18.  
  19. #ifdef __MSDOS__
  20. #include <io.h>
  21. #include <alloc.h>
  22. #include <sys\stat.h>
  23. #else
  24. #include <sys/types.h>
  25. #include <sys/stat.h>
  26. #endif /* __MSDOS__ */
  27.  
  28. #include <fcntl.h>
  29. #include <stdio.h>
  30. #include <string.h>
  31. #include "gif_lib.h"
  32. #include "gif_hash.h"
  33.  
  34. #define PROGRAM_NAME    "GIF_LIBRARY"
  35.  
  36. /* #define  DEBUG_HIT_RATE    Debug number of misses per hash Insert/Exists. */
  37.  
  38. #ifdef    DEBUG_HIT_RATE
  39. static long NumberOfTests = 0,
  40.         NumberOfMisses = 0;
  41. #endif    /* DEBUG_HIT_RATE */
  42.  
  43. #ifdef SYSV
  44. static char *VersionStr =
  45.         "Gif library module,\t\tGershon Elber\n\
  46.     (C) Copyright 1989 Gershon Elber, Non commercial use only.\n";
  47. #else
  48. static char *VersionStr =
  49.     PROGRAM_NAME
  50.     "    IBMPC "
  51.     GIF_LIB_VERSION
  52.     "    Gershon Elber,    "
  53.     __DATE__ ",   " __TIME__ "\n"
  54.     "(C) Copyright 1989 Gershon Elber, Non commercial use only.\n";
  55. #endif /* SYSV */
  56.  
  57. static int KeyItem(unsigned long Item);
  58.  
  59. /******************************************************************************
  60. * Initialize HashTable - allocate the memory needed and clear it.          *
  61. ******************************************************************************/
  62. GifHashTableType *_InitHashTable(void)
  63. {
  64.     GifHashTableType *HashTable;
  65.  
  66.     if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType)))
  67.     == NULL)
  68.     return NULL;
  69.  
  70.     _ClearHashTable(HashTable);
  71.  
  72.     return HashTable;
  73. }
  74.  
  75. /******************************************************************************
  76. * Routine to clear the HashTable to an empty state.                  *
  77. * This part is a little machine depended. Use the commented part otherwise.   *
  78. ******************************************************************************/
  79. void _ClearHashTable(GifHashTableType *HashTable)
  80. {
  81.     memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(long));
  82. }
  83.  
  84. /******************************************************************************
  85. * Routine to insert a new Item into the HashTable. The data is assumed to be  *
  86. * new one.                                      *
  87. ******************************************************************************/
  88. void _InsertHashTable(GifHashTableType *HashTable, unsigned long Key, int Code)
  89. {
  90.     int HKey = KeyItem(Key);
  91.     unsigned long *HTable = HashTable -> HTable;
  92.  
  93. #ifdef DEBUG_HIT_RATE
  94.     NumberOfTests++;
  95.     NumberOfMisses++;
  96. #endif /* DEBUG_HIT_RATE */
  97.  
  98.     while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) {
  99. #ifdef DEBUG_HIT_RATE
  100.         NumberOfMisses++;
  101. #endif /* DEBUG_HIT_RATE */
  102.     HKey = (HKey + 1) & HT_KEY_MASK;
  103.     }
  104.     HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code);
  105. }
  106.  
  107. /******************************************************************************
  108. * Routine to test if given Key exists in HashTable and if so returns its code *
  109. * Returns the Code if key was found, -1 if not.                      *
  110. ******************************************************************************/
  111. int _ExistsHashTable(GifHashTableType *HashTable, unsigned long Key)
  112. {
  113.     int HKey = KeyItem(Key);
  114.     unsigned long *HTable = HashTable -> HTable, HTKey;
  115.  
  116. #ifdef DEBUG_HIT_RATE
  117.     NumberOfTests++;
  118.     NumberOfMisses++;
  119. #endif /* DEBUG_HIT_RATE */
  120.  
  121.     while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) {
  122. #ifdef DEBUG_HIT_RATE
  123.         NumberOfMisses++;
  124. #endif /* DEBUG_HIT_RATE */
  125.     if (Key == HTKey) return HT_GET_CODE(HTable[HKey]);
  126.     HKey = (HKey + 1) & HT_KEY_MASK;
  127.     }
  128.  
  129.     return -1;
  130. }
  131.  
  132. /******************************************************************************
  133. * Routine to generate an HKey for the hashtable out of the given unique key.  *
  134. * The given Key is assumed to be 20 bits as follows: lower 8 bits are the     *
  135. * new postfix character, while the upper 12 bits are the prefix code.          *
  136. * Because the average hit ratio is only 2 (2 hash references per entry),      *
  137. * evaluating more complex keys (such as twin prime keys) does not worth it!   *
  138. ******************************************************************************/
  139. static int KeyItem(unsigned long Item)
  140. {
  141.     return ((Item >> 12) ^ Item) & HT_KEY_MASK;
  142. }
  143.  
  144. #ifdef    DEBUG_HIT_RATE
  145. /******************************************************************************
  146. * Debugging routine to print the hit ratio - number of times the hash table   *
  147. * was tested per operation. This routine was used to test the KeyItem routine *
  148. ******************************************************************************/
  149. void HashTablePrintHitRatio(void)
  150. {
  151.     printf("Hash Table Hit Ratio is %ld/%ld = %ld%%.\n",
  152.     NumberOfMisses, NumberOfTests,
  153.     NumberOfMisses * 100 / NumberOfTests);
  154. }
  155. #endif    /* DEBUG_HIT_RATE */
  156.